#include <bits/stdc++.h>
using namespace std;

using vvint=vector<vector<int>>;
//这道题和39题一样，加一个bool数组剪枝即可
/*
 *class Solution {
 *public:
 *    void dfs(vvint& ret,vector<int>& nums,int target,
 *        vector<int>& temp,vector<bool>& use,int index,int pos)
 *    {
 *        if(pos==target)
 *        {
 *            ret.push_back(temp);
 *            return;
 *        }
 *        for(int i=index;i<nums.size();i++)
 *        {
 *            if(use[i])continue;
 *            //use[i-1]一定是使用了并且恢复false的，此时说明已经添加到
 *            //temp中了，所以要判断use[i-1]，如果use[i-1]还是true，
 *            //继续判断下一个即可
 *            if(i>0&&!use[i-1]&&nums[i]==nums[i-1])continue;      
 *            if(pos+nums[i]>target)continue;   
 *
 *            pos+=nums[i];
 *            temp.push_back(nums[i]);
 *            use[i]=true;
 *
 *            dfs(ret,nums,target,temp,use,i+1,pos);
 *
 *            pos-=nums[i];
 *            temp.pop_back();
 *            use[i]=false;
 *        }
 *    } 
 *    vvint combinationSum2(vector<int>& nums, int target) {
 *        sort(nums.begin(),nums.end());
 *        vvint ret;
 *        vector<int> temp;
 *        vector<bool> use(nums.size(),false);
 *        dfs(ret,nums,target,temp,use,0,0);
 *        return ret;
 *    }
 *};
 */


//高精度加法
class Solution {
public:

    string multiply(string num1, string num2) {
        if(num1[0]=='0'||num2[0]=='0')return "0";
        string retstring;
        int len1=num1.size(),len2=num2.size(),j=len2-1;
        vector<int> ret(len1+len2,0);
        while(j>=0)
        {
            for(int i=len1-1;i>=0;i--)
            {
                int here=(num1[i]-'0')*(num2[j]-'0');
                int sum=ret[i+j+1]+here;//进位
                ret[i+j+1]=sum%10;
                ret[i+j]+=sum/10;
            }
            j--;
        }
        int start=0;
        while(start<ret.size()&&ret[start]==0)start++;
        for(int i=start;i<ret.size();i++)
            retstring+=to_string(ret[i]);
        return retstring;
    }
};
